1. Field of the Invention
This invention relates to a method for and a system of decoding compressed digital image data of source image, such as still or motion images, or multiple-valued images of computer graphics or the like.
2. Description of the Prior Art
Heretofore, coding and decoding of a source image to and from compressed digital image data are usually done with a system, in which orthogonal transformation, quantization and entropy coding are combined. A prior art example of still picture coding and decoding to and from compressed digital image data, will now be described with reference to FIGS. 1 to 6.
FIG. 1 shows the structure of a prior art system for compression coding a source image. Referring to the Figure, designated at 1 is an input source image, at 2 is an 8.times.8 sample block of the source image, at 3 a compressor for compressing the 8.times.8 sample block, and at 4 compressed image data obtained from the compressor 3. The compressor 3 comprises units 5 to 8.
The unit 5 performs a two-dimensional orthogonal transform process, that is, it does two-dimensional orthogonal transform of the 8.times.8 sample block. The unit 6 performs a quantization process, that is, it quantizes individual elements of a coefficient matrix obtained in the two-dimensional orthogonal transform process unit 5. The unit 7 performs a zig-zag scan process, that is, it produces a coefficient row of quantized coefficient matrix elements arranged from the lower order. The unit 8 performs an entropy coding process, that is, it codes the coefficient row with Huffman codes, for instance.
Now, the prior art procedure of a compression of source image will be described.
First, a source image 1 on a frame memory is divided into 8.times.8 pel blocks, and a sample block is extracted. Then, the two-dimensional orthogonal transform process unit 5 effects transform of the aggregate of pels in the block into a two-dimensional frequency space coefficient matrix (of 8.times.8 elements) using the discrete cosine transform (DCT) which is one type of orthogonal transform. The transform is done with a formula (1): ##EQU1## where C(0)=0.707 and C(n)=1.0 (n=1 to 7). Further, P(x, y) represents the pel values of the 8.times.8 sample block, and Z(u, v) represents the coefficient values of the 8.times.8 pel DCT coefficient matrix.
In the coefficient matrix Z(u, v) obtained with the above transform formula, Z(0, 0) represents a DC component, and other Z(u, v) represents AC components.
The quantization process unit 6 quantizes the individual elements in the obtained coefficient matrix Z(u, v) by dividing these elements by elements in the quantization matrix (of 8.times.8 elements) of the same size as shown in FIG. 2. Of the result of the division, the integral number part is retained, and the remainder is omitted.
In the quantization matrix, as shown in FIG. 2, the higher the frequency of a portion in the coefficient matrix Z(u, v), the numerical value, i.e., the quantization step span, is the greater, and the quantization matrix serves the role of a filter for reducing the high frequency components of the image. More specifically, the left upper part of the quantization matrix shown in FIG. 2 corresponds to low frequency range, while the right lower part corresponds to high frequency range. Thus, it will be seen that the numerical values are greater as one goes from the left top to the right bottom of the quantization matrix.
The individual elements in the quantized coefficient matrix Z(u, v) are rearranged in the order of serial numbers shown in a zig-zag scan matrix in FIG. 3. FIG. 4 shows the manner, in which individual elements S0, S1, . . . of the quantized coefficient matrix Z(u, v) are rearranged, and the manner in which the rearranged elements are coded using Huffman codes which are one type of entropy coding. Si (i=0, 1, . . . ) represents compressed data obtained as a result of coding using Huffman codes. [EOB] is a Huffman code indicating that the remaining coefficients are all "0", that is, it indicates the end of block.
The coding of the DC component SO in the coefficient matrix Z(u, v) shown in FIG. 4, is done by classifying inter-block differences in occurrence frequency groups and adding a Huffman code corresponding to a group and a bit row necessary for expressing the pertaining difference. On the other hand, the coding of the AC components S1 is done by classifying sets each of a non-"0" coefficient value in the rearranged coefficient matrix and the number of preceding "0" coefficients in occurrence frequency groups and adding a Huffman code corresponding to a group and a bit row necessary for expressing the pertaining non-"0" coefficient value.
Since the high frequency reduction filter is provided for each element in the coefficient matrix Z(u, v) as noted above, the elements in the rearranged coefficient matrix are often "0" from a certain position to the end of block. In such a case, the Huffman code [EOB] representing the end of block is added after the last non-"0" coefficient, and the Huffman coding of the subsequent coefficients is omitted.
A specific example of coding will now be described with reference to FIG. 5. In FIG. 5, 4.times.4 pel block is taken as an example instead of 8.times.8 pel block for easier understanding of the description. A coefficient matrix Z(u, v), shown at 51, obtained by applying the formula (1) noted above to 4.times.4 pel block P(x, y) not shown, is divided by corresponding elements in the quantization matrix 52, as shown at 53. The remainder of the quotient of each division is omitted, thus forming a quantized coefficient matrix 54 consisting of integral elements. The elements of the quantized coefficient matrix 54 are rearranged in the order of the elements in the zig-zag scan matrix 55 to obtain a quantized coefficient matrix 56. This quantized coefficient matrix 56 is then entropy coded. Thus, an entropy coded row as shown in FIG. 4 is obtained.
Now, the structure of the prior art system of decoding compressed digital image data of a source image will be described with reference to FIG. 6. Referring to FIG. 6, designated at 10 is a compressed image data decoder, at 11 an 8.times.8 sample block of decoded image, and at 12 a reproduced image. The decoder 10 comprises units 13 to 16.
The unit 13 performs an entropy decoding process, that is, it decodes compressed image data coded with Huffman codes or the like. The unit 14 performs a zig-zag scan process, that is, it produces an 8.times.8 element coefficient matrix from quantized coefficient row of elements arranged from lower orders. The unit 15 performs an inverse quantization process, that is, it inversely quantizes the quantized coefficient matrix. The unit 16 performs a two-dimensional inverse orthogonal transform process, that is, it effects two-dimensional inverse orthogonal transform of the reproduced coefficient matrix to reproduce the 8.times.8 pel block of the source image.
Now, the prior art procedure of decoding compressed image data of source image will be shown. The decoding procedure is inverse to the coding procedure.
The entropy decoding process unit 13 decodes Huffman codes. The zig-zag scan process unit 14 rearranges the coefficient row obtained by the decoding in the order of smaller serial numbers shown in the zig-zag scan matrix of FIG. 3. When a Huffman code [EOB] indicative of the end of block appears, the subsequent coefficients are made "0", thus reproducing the quantized coefficient matrix (of 8.times.8 elements).
Then, the inverse quantization process unit 15 effects inverse quantizing by multiplying the individual elements in the quantized coefficient matrix by the elements in the same quantization matrix as that used in encoding (see FIG. 2). As a result of tills inverse quantizing, the two-dimensional frequency space coefficient matrix is reproduced.
Then, the two-dimensional inverse orthogonal transform process unit 16 effects inverse discrete cosine transform (IDCT) of the two-dimensional frequency space coefficient matrix to reproduce the 8.times.8 sample block 11 of source image. The entire source image is reproduced by iteration of the reproduction of the above 8.times.8 sample block.
The inverse orthogonal transform in the two-dimensional inverse orthogonal transform process unit 16 involves an enormous quantity of operations if it is executed as specified by the definition formula. To obtain fast operation, FFT (fast Fourier transform) or like fast operation processes have heretofore been proposed. However, even such methods may not permit sufficiently fast processing to be obtained when the two-dimensional orthogonal transform is done on a large number of blocks as in image compression.